/**
 * 图的顺序存储结构
 */
#include <stdio.h>
#include <stdlib.h>

typedef enum{DG, DN, UDG, UDN} GraphKind;	//枚举图的四种类型

//顶点关系结构体
typedef struct{
	int adj;		//对于无权图,1代表相邻,0代表不相邻
	char* info;		//边上的额外信息
}AdjMatrix[20][20];	//顶点矩阵

typedef struct{
	int vertexIndexArray[20];	//存储图中的顶点的索引
	AdjMatrix adjArray;			//二维数组，用来记录顶点之间的关系
	int vertex_num, arch_num;	//记录图中顶点数目以及边的数目
	GraphKind kind;				//记录图的类型
}MGraph;

//创建一个图
void CreateGraph(MGraph* G);

//根据结点的值找出结点在索引数组中的位置
int LocateVertex(MGraph* G, int vertex);

//打印函数
void PrintGraph(MGraph* G);

//构造无向图
void CreateDN(MGraph* G);

//构造无向网(和无向图唯一的区别是二阶矩阵存储的是边的权值)
void CreateUDN(MGraph* G);

//构造有向图
void CreateDG(MGraph* G);

//构造有向网
void CreateUDG(MGraph* G);

int main()
{
	MGraph G;	//建立一个图变量
	CreateGraph(&G);	
	PrintGraph(&G);	//输出图的二维矩阵
	return 0;
}

void CreateDN(MGraph* G)
{
	printf("请输入要构建无向图的顶点数和边数: ");
	scanf("%d %d",&(G->vertex_num),&(G->arch_num));
	//为无向图的每个顶点赋值
	for(int i=0;i<G->vertex_num;i++)
	{
		printf("请输入第%d个结点的值",i+1);
		scanf("%d",&(G->vertexIndexArray[i]));
	}
	
	//初始化无向图之间的关系(是否相邻),默认都不相邻
	for(int i=0;i<G->vertex_num;i++)
	{
		for(int j=0; j<G->vertex_num;j++)
		{
			G->adjArray[i][j].adj=0;
			G->adjArray[i][j].info=NULL;
		}
	}
	
	//确定无向图中结点与结点之间的关系(是否相邻->有边)
	int vertex1,vertex2;
	printf("请输入结点vertex1, vertex2: ");
	scanf("%d %d",&vertex1, &vertex2);
	
	int vertex1_index=LocateVertex(G, vertex1);
	int vertex2_index=LocateVertex(G, vertex2);
	if(vertex1_index==-1 || vertex2_index==-1)
	{
		printf("要创建边的结点不存在\n");
		return;
	}
	
	//无向图的邻接表矩阵具有对称性
	G->adjArray[vertex1_index][vertex2_index].adj=1;
	G->adjArray[vertex2_index][vertex1_index].adj=1;
}

/**
 * @brief 找到就返回索引位置，找不到就返回-1
 * 
 * @param G 
 * @param vertex 
 * 
 * @return 
 */
int LocateVertex(MGraph* G, int vertex)
{
	//遍历一维数组找到要查询的结点在索引数组中的位置
	for(int i=0;i<G->vertex_num;i++)
	{
		//如果找到则返回i
		if(G->vertexIndexArray[i]==vertex) return i;
	}
	return -1;	//好不到就返回-1
}

void CreateGraph(MGraph* G)
{
	//选择图的类型
	scanf("%d", &(G->kind));
	switch (G->kind) {
	case DG:
		return CreateDG(G);
		break;
	case DN:
		return CreateDN(G);
		break;
	case UDG:
		return CreateUDG(G);
		break;
	case UDN:
		return CreateUDN(G);
		break;
	default:
		break;
	}
	
}

void PrintGraph(MGraph* G)
{
	printf("图中各顶点之间的关系为:\n");
	for(int i=0;i<G->vertex_num;i++)
	{
		for(int j=0;j<G->vertex_num;j++)
		{
			printf("%d ",G->adjArray[i][j].adj);
		}
		printf("\n");
	}
}

void CreateUDN(MGraph* G)
{
	printf("请输入要构建无向网的顶点数和边数:");
	scanf("%d %d",&(G->vertex_num),&(G->arch_num));
	//初始化顶点索引数组
	for(int i=0;i<G->vertex_num;i++)
	{
		printf("请输入第%d个顶点的值",i+1);
		scanf("%d", &(G->vertexIndexArray[i]));
	}
	
	//初始化顶点与顶点权值二维数组(默认权值都是0)
	for(int i=0;i<G->vertex_num;i++)
	{
		for(int j=0;j<G->vertex_num;j++)
		{
			G->adjArray[i][j].adj=0;
			G->adjArray[i][j].info=NULL;
		}
	}
	
	//为边赋权值
	for(int i=0;i<G->arch_num;i++)
	{
		int vertex1,vertex2,weight;	//weight为vertex1和vertex2两个顶点之间的权值
		scanf("%d %d %d",&vertex1, &vertex2, &weight);
		//寻找出vertex1和vertex2在索引数组中的下标
		int vertex1_index=LocateVertex(G, vertex1_index);
		int vertex2_index=LocateVertex(G, vertex2_index);
		
		if(vertex1_index==-1 || vertex2_index==-1)
		{
			printf("该无向网中没有该结点\n");
			return;
		}
		
		G->adjArray[vertex1_index][vertex2_index].adj=weight;
		G->adjArray[vertex2_index][vertex1_index].adj=weight;	//无向图的矩阵对称性
	}	
}

void CreateDG(MGraph* G)
{
	printf("输入图中含有的顶点数目和边数:");
	scanf("%d %d", &(G->vertex_num), &(G->arch_num));
	//初始化顶点索引数组
	for(int i=0;i<G->vertex_num;i++)
	{
		scanf("%d", &(G->vertexIndexArray[i]));
	}
	
	//初始化而为关系矩阵,默认关系为0
	for(int i=0;i<G->vertex_num;i++)
	{
		for(int j=0; j<G->vertex_num;j++)
		{
			G->adjArray[i][j].adj=0;
			G->adjArray[i][j].info=NULL;
		}
	}
	
	//在二维数组中添加弧的数据(列代表头，行代表尾)
	for(int i=0;i<G->arch_num;i++)
	{
		int vertex_head,vertex_end;	//vertex_head代表弧头,vertex_end代表弧尾
		printf("请输入弧头和弧尾:");
		scanf("%d %d",&vertex_head,&vertex_end);
		int vertex_head_index=LocateVertex(G,vertex_head);
		int vertex_end_index=LocateVertex(G,vertex_end);
		if(vertex_head_index==-1 || vertex_end_index==-1)
		{
			printf("没有该结点\n");
			return;
		}
		
		//将弧头和弧尾写入二维数组中
		G->adjArray[vertex_head_index][vertex_end_index].adj=1;
	}
}

void CreateUDG(MGraph* G)
{
	printf("请输入有向网的顶点的个数和边的个数:");
	scanf("%d %d", &(G->vertex_num), &(G->arch_num));
	for(int i=0;i<G->vertex_num;i++)
	{
		printf("请输入第%d个结点:",i+1);
		scanf("%d",&(G->vertexIndexArray[i]));
	}
	
	for(int i=0;i<G->vertex_num;i++)
	{
		for(int j=0;j<G->vertex_num;j++)
		{
			G->adjArray[i][j].adj=0;
			G->adjArray[i][j].info=NULL;
		}
	}
	
	for(int i=0;i<G->arch_num;i++)
	{
		int vertex_head,vertex_end,weight;	//weight为vertex_head和vertex_end之间的权重
		scanf("%d %d %d",&vertex_head,&vertex_end,&weight);
		int vertex_head_index=LocateVertex(G,vertex_head);
		int vertex_end_index=LocateVertex(G, vertex_end);
		if(vertex_end_index==-1 || vertex_head_index==-1)
		{
			printf("结点不合法\n");
			return;
		}
		
		G->adjArray[vertex_head_index][vertex_end_index].adj=weight;
	}
}